package code.oldCode.feishuSpecializedTraining.hash;

import java.util.*;

/**
 * @author 26029
 * @date 2025/3/8
 * @description
 */
public class MyHash2 {
    // 454. 四数相加 II
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int len = nums1.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int num = nums1[i] + nums2[j];
                if (!hashMap.containsKey(num)) {
                    hashMap.put(num, 1);
                } else {
                    hashMap.put(num, hashMap.get(num) + 1);
                }
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int num = - (nums3[i] + nums4[j]);
                if (hashMap.containsKey(num)) {
                    ans += hashMap.get(num);
                }
            }
        }
        return ans;
    }

    // 383. 赎金信
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int len = magazine.length();
        for (int i = 0; i < len; i++) {
            Character c = magazine.charAt(i);
            if (hashMap.containsKey(c))
                hashMap.put(c, hashMap.get(c) + 1);
            else
                hashMap.put(c, 1);
        }
        len = ransomNote.length();
        for (int i = 0; i < len; i++) {
            Character c = ransomNote.charAt(i);
            if (hashMap.containsKey(c)) {
                if (hashMap.get(c) == 1)
                    hashMap.remove(c);
                else
                    hashMap.put(c, hashMap.get(c) - 1);
            } else {
                return false;
            }
        }
        return true;
    }

    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        // 提前建立HashMap法，O(n^2)
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            hashMap.put(nums[i], i);
        }
        for (int i = 0; i < len - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < len - 1; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1])
                    continue;
                // 找第三个
                int target = - (nums[i] + nums[j]);
                if (hashMap.containsKey(target) && hashMap.get(target) > j) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(target);
                    lists.add(list);
                }
            }
        }
        return lists;
    }

    public List<List<Integer>> threeSum_(int[] nums) {
        // 双指针法，也是O(n^2)，官解神人做法，不如自己的如下
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < len - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int target = -nums[i];
            int right = len - 1;
            for (int left = i + 1; left < len; left++) {
                if (left != i + 1 && nums[left] == nums[left - 1])
                    continue;
                while (left < right && nums[left] + nums[right] > target)
                    right--;
                if (left == right)
                    break;
                if (nums[left] + nums[right] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(-target);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }
    public List<List<Integer>> threeSum__(int[] nums) {
        // 双指针法，也是O(n^2)，更好理解的做法
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < len - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int target = -nums[i];
            int left = i + 1, right = len - 1;
            while (left < right) {
                int numL = nums[left], numR = nums[right];
                if (numL + numR == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(-target);
                    list.add(numL);
                    list.add(numR);
                    lists.add(list);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (numL + numR < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return lists;
    }

    // 18. 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 被int溢出用例弄麻了，故用long，有一些剪枝操作可以学习一下
        int len = nums.length;
        Arrays.sort(nums);
        HashMap<Long, Integer> hashMap = new HashMap<>();
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            hashMap.put((long)nums[i], i);
        }
        for (int i = 0; i < len - 3; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;

            // 剪枝
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > (long) target)
                break;
            if ((long) nums[i] + nums[len -3] + nums[len - 2] + nums[len - 1] < (long) target)
                continue;

            for (int j = i + 1; j < len - 2; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1])
                    continue;

                // 剪枝
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > (long) target)
                    break;
                if ((long) nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < (long) target)
                    continue;

                for (int k = j + 1; k < len - 1; k++) {
                    if (k != j + 1 && nums[k] == nums[k - 1])
                        continue;
                    long find = (long) target - ((long)nums[i] + nums[j] + nums[k]);
                    if (hashMap.containsKey(find) && hashMap.get(find) > k) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        list.add((int)find);
                        lists.add(list);
                    }
                }
            }
        }
        return lists;
    }
}
